西北师范大学2008年普通专升本招生计算机科学与技术专业

考试大纲

（试行）

一、考试目的

西北师范大学专升本招生《计算机科学与技术专业》专业综合课包括两部分内容：数据结构和操作系统。考试目的是检查学生是否牢固掌握《数据结构》和《操作系统》两门课程相关知识的一次水平测定，全面考核普通高校计算机专科（含高职）应届毕业生对专业核心课程《数据结构》和《操作系统》的掌握程度，要求学生比较系统地理解数据结构和操作系统的基本概念和基本理论。

二、考试内容

（数据结构部分）

（一）数据结构的概念

   1. 什么是数据结构（逻辑结构，存储结构，运算）；

   2. 算法，算法分析，算法特性；

   3.算法与程序的差别。

（二）顺序表

   1.线性表（向量）的定义，操作，算法；

   2.栈的定义，操作，算法；

3.队列的定义，操作，算法。

（三）链表

   1.链表的概念及其特点；

   2.单链表的概念，存储表示，查找，输入，删除等运算和算法；

3.双链表的概念，存储表示，查找，输入，删除等运算和算法。

（四）排序

   1.排序的概念，内排序和外排序，排序算法的稳定性；

   2.内排序的分类；

   3.各种排序的基本思想，例子，算法，稳定性，时空复杂度。

（五）线性表的检索

1.顺序检索的概念，算法，时间复杂度；

2.二分检索的概念，算法，时间复杂度；

   3.散列法：（1）基本概念；

            （2）散列函数的构造方法；

            （3）冲突的处理：拉链法，开地址法，算法。

（六）树形结构

   1.树和二叉树的概念；

   2.树（林）与二叉树的相互转换；

   3.二叉树的存储表示（1）二叉链表（2）完全二叉树的顺序存储；

   4.二叉树与树的周游（遍历）的概念，各种周游方法；

   5.二叉树遍历的算法；

   6.二叉树中其他算法（结点统计，高度计算，左右子树交换等）。

（七）树表检索

   1.二叉排序树的概念，插入，删除运算；

   2.最佳二叉排序树的概念，建立方法，算法；

   3.平衡二叉排序树（AVL）的概念，构造方法（如何调整。）

（八）图

   1.图的概念和相关术语；

   2.图的存储表示方法：邻接矩阵，邻接表，邻接多重表；

   3.图的遍历： 深度优先遍历，广度优先遍历；

   4.最小生成树的概念，构造方法，算法；

   5.拓扑排序的概念，算法思想，算法；

   6.最短路径的概念，构造方法，算法。

（操作系统部分）

（一）操作系统的基本概念

1. 理解操作系统的定义、特征就及设置操作系统的目的；

2. 了解操作系统在计算机系统中的地位、操作系统的形成和发展；

3. 掌握多道程序设计和虚拟处理机的基本原理；

4. 了解操作系统的分类；掌握分时系统的特征。

5. 了解研究操作系统的几种不同观点。

（二）用户与操作系统的接口

1. 理解作业，作业步，作业流的概念；

2. 掌握脱机作业控制方式，联机作业控制方式；

3. 了解系统功能调用。

（三）作业管理

1. 理解并掌握作业管理的基本功能；

2. 理解并掌握作业控制的两种方式；

3.掌握批处理作业的几种调度算法以及作业调度和进程调度的关系；

4. 掌握脱机输入输出和SPOOLING 技术；

5. 了解作业控制块和作业后备队列。

（四）进程管理

1. 理解并掌握程序的并发执行和资源共享；

2. 掌握程序并发执行的特性；

3. 理解并掌握进程的概念、进程的表示和调度状态；

4. 了解进程的控制机构及进程控制原语；

5. 熟练掌握常用的进程调度算法（静态优先级法，动态优先级法，时间片轮转法）；

6. 熟练掌握作业，进程，和程序之间的区别和联系；

7. 理解并掌握进程间的同步与互斥；

8. 理解信号量及P，V操作，并能利用信号量机制实现进程间的同步与互斥；

9.  理解并熟练掌握利用信号量机制实现的生产者——消费者问题；

10.了解高级通讯原语（消息缓冲方式，信箱方式）；

11. 理解并掌握死锁的概念、起因及产生死锁的必要条件；

12. 了解处理死锁的四种对策（预防策略，避免策略，检测和解除）；

13．了解单项资源的银行家算法和多种资源的银行家算法；

（五）存储管理

1. 理解并掌握存储管理的基本概念功能及物理地址和逻辑地址之间的关系；

2. 了解早期计算机系统中主要采用的单一连续分配，分区分配，覆盖和交换的存储管理方案；

3. 理解并掌握页式、段式和段页式虚拟存储管理的基本原理和地址转换关系；

4. 理解并熟练掌握各种页面置换算法（FIFO，LRU，LRU近似算法）。

（六）文件管理系统

1. 理解文件和文件系统的概念；

2. 了解文件的基本类型及文件系统的基本功能；

3. 理解文件的逻辑结构（记录式文件，流式文件）；

4. 理解文件的物理结构（连续结构，串连结构，索引文件）；

5. 掌握文件的存取方法（顺序存取法，直接存取法，按键存取法）；

6. 理解文件结构，文件存储设备和存取法的关系；

7.掌握简单的文件目录，二级目录，多级目录；

8. 掌握文件存储空间管理的各种办法；

9. 掌握文件存取控制的各种方法；

10. 了解文件系统和用户间的接口。

（七）设备管理

1. 了解I/O设备类型及设备管理的设计目标；

2.了解设备管理的基本功能；

3. 掌握I/O控制的几种方式；

4. 掌握通道功能及类型；

5. 了解通道命令和通道程序；

6. 了解顺序存取存储设备，直接存取存储设备;

7. 掌握磁盘的驱动调度算法。

（八）常用操作系统

了解DOS操作系统、WINDOWS操作系统和UNIX操作系统的概念和基本命令。

三、试题难易度

较容易题                      约30%

中等难度题                    约50%

较难题                        约20%

四、说明

试卷满分为200分，《数据结构》和《操作系统》各100分，考试时间为180分钟。